/*
 * Description: LRU cache
 */

#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include <unordered_map>
#include <list>

template <typename K, typename V = K>
class LRUCache {
public:
    explicit LRUCache(int size) : cap(size)
    {}

    ~LRUCache() = default;

    void Set(const K key, const V value)
    {
        auto pos = kvMap.find(key);
        if (pos == kvMap.end()) {
            keyList.push_front(key);
            kvMap[key] = {value, keyList.begin()};
            if (kvMap.size() > cap) {
                kvMap.erase(keyList.back());
                keyList.pop_back();
            }
        } else {
            keyList.erase(pos->second.second);
            keyList.push_front(key);
            kvMap[key] = {value, keyList.begin()};
        }
    }

    bool Get(const K key, V &value)
    {
        auto pos = Find(key);
        if (pos == kvMap.end()) {
            return false;
        }
        value = pos->second.first;
        return true;
    }

    bool Exist(const K key)
    {
        return Find(key) != kvMap.end();
    }

private:
    typename std::unordered_map<K, std::pair<V, typename std::list<K>::iterator>>::iterator Find(const K key)
    {
        auto pos = kvMap.find(key);
        if (pos != kvMap.end()) {
            keyList.erase(pos->second.second);
            keyList.push_front(key);
            kvMap[key] = {pos->second.first, keyList.begin()};
        }
        return pos;
    }

    std::list<K> keyList;
    std::unordered_map<K, std::pair<V, typename std::list<K>::iterator>> kvMap;
    int cap;
};

#endif  // LRU_CACHE_H
